Fonction semi-lisse

En analyse mathématique, la semi-lissité d'une fonction est un concept de différentiabilité plus faible que celui de Fréchet, qui permet toutefois d'assurer la convergence locale de l'algorithme de Newton lorsque l'opérateur dérivée est remplacé par un élément inversible du différentiel de Clarke. L'algorithme correspondant est connu sous le nom de méthode de Newton semi-lisse.

La semi-lissité est stable pour beaucoup d'opérations habituelles (addition, produit scalaire, composition, ...) mais aussi pour la prise de minimum et de maximum, ce qui rend cette propriété attractive dans beaucoup de problèmes.

Définitions

Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces vectoriels réels de dimension finie, $\Omega$ un ouvert de $\mathbb {E}$ et $F:\Omega \to \mathbb {F}$ une fonction non lisse (c'est-à-dire non différentiable au sens de Fréchet), mais toutefois localement lipschitzienne sur $\Omega$ et donc avec un différentiel de Clarke non vide aux points de $\Omega$. On note ce dernier en $x$ par $\partial _{C}F(x)$.

Motivation

Les définitions sont motivées par le souhait de faire converger plus ou moins rapidement la suite générée par une version adaptée de l'algorithme de Newton pour trouver une zéro $x_{*}$ du système d'équations non lisses

$F(x)=0.$

La version généralisée de l'algorithme de Newton que l'on considère, appelée méthode de Newton semi-lisse, s'écrit

$x_{k+1}:=x_{k}-J_{k}^{-1}F(x_{k}),$

où $J_{k}$ est une jacobienne inversible de $\partial _{C}F(x_{k})$, qui est supposée exister.

On cherche à faire converger les itérés $x_{k}$ en se fondant sur le calcul suivant :

${\begin{array}{rcl}x_{k+1}-x_{*}&=&x_{k}-x_{*}-J_{k}^{-1}F(x_{k})\\&=&-J_{k}^{-1}{\bigl [}F(x_{k})-F(x_{*})-J_{k}(x_{k}-x_{*}){\bigr ]}\\&=&-J_{k}^{-1}{\bigl [}F(x_{*}+h_{k})-F(x_{*})-J_{k}h_{k}{\bigr ]},\end{array}}$

où l'on a noté $h_{k}:=x_{k}-x_{*}$. Dès lors, si $\{J_{k}^{-1}\}$ est bornée et si

$F(x_{*}+h_{k})-F(x_{*})-J_{k}h_{k}=o(\|h_{k}\|)$

la convergence superlinéaire de la suite $\{x_{k}\}$ est assurée. C'est précisément cette dernière estimation qui est requise dans la définition de la semi-lissité. On remarquera bien que $J_{k}$ est une jacobienne généralisée en $x_{*}+h_{k}$, et pas en $x_{*}$, comme on pourrait être tenté de l'imposer en s'inspirant de la Fréchet-différentiabilité.

Semi-lissité

La définition de la semi-lissité requiert un peu plus que l'estimation de $F(x_{*}+h_{k})-F(x_{*})-Jh$ donnée dans la section «Motivation», car on souhaite que cette propriété puisse se conserver après diverses opérations.

Semi-lissité — On dit que $F$ est semi-lisse en $x\in \mathbb {E}$ si

• $F$ est lipschitzienne dans un voisinage de $x$,
• $F$ admet des dérivées directionnelles en $x$ dans toutes les directions,
• lorsque $h\to 0$, on a

$\sup _{J\in \partial _{C}F(x+h)}\;\|F(x+h)-F(x)-Jh\|=o(\|h\|).$

On dit que $F$ est fortement semi-lisse en $x$ si elle est semi-lisse en $x$ avec le point 3 ci-dessus renforcé en

• pour $h$ voisin de $0$, on a

$\sup _{J\in \partial _{C}F(x+h)}\;\|F(x+h)-F(x)-Jh\|=O(\|h\|^{2}).$

On dit que $F$ est (fortement) semi-lisse sur $\Omega$ de $\mathbb {E}$ si elle est (fortement) semi-lisse en tout point de $\Omega$.

Quelques remarques.

• La lipschitziannité de $F$ dans le voisinage de $x$ assure que le différentiel de Clarke $\partial _{C}F(x)$ est non vide et compact. On peut donc l'utiliser dans la suite de la définition.
• L'existence de dérivées directionnelles est demandée pour assurer de bonnes propriétés à la notion de dérivabilité semi-lisse.
• Comme annoncé dans la section «Motivation», dans l'estimation de $F(x+h)-F(x)-Jh$, les jacobiennes $J$ sont prises dans le différentiel en $x+h$, pas en $x$.

La notion de semi-lissité a été introduite par Mifflin (1977) pour les fonctions à valeurs scalaires et étendue aux fonctions à valeurs vectorielles par Qi et Sun (1993).

Propriétés

Propriétés générales

Une fonction de classe $C^{1}$ est semi-lisse.

Différentiabilité et semi-lissité — Si $F:\Omega \to \mathbb {F}$ est de classe $C^{1}$ (resp. $C^{1,1}$) dans un voisinage de $x$, alors elle est semi-lisse (resp. fortement semi-lisse) en $x$.

Une fonction convexe est aussi semi-lisse.

Semi-lissité d'une fonction convexe — Si $F:\Omega \to \mathbb {R}$ est convexe dans un voisinage convexe de $x\in \Omega$, alors elle est semi-lisse en $x$.

Dans la proposition ci-dessous, on dit que $F:\Omega \to \mathbb {F}$ est semi-lisse par morceaux en $x\in \Omega$, s'il existe un voisinage $V$ de $x$ et des fonctions semi-lisses $F_{i}:V\to \mathbb {F}$, pour $i\in I$ avec $|I|$ est fini, tels que :

• $F$ est continue sur $V$,
• pour tout $x'\in V$, il existe un indice $i\in I$ tel que $F(x')=F_{i}(x')$.

Semi-lissité par morceaux — Si $F:\Omega \to \mathbb {F}$ est semi-lisse par morceaux en $x\in \Omega$, alors $F$ est semi-lisse en $x$.

Lorsque les morceaux sont affines, on dit que la fonction est affine par morceaux en $x$.

Affinité par morceaux — Si $F:\Omega \to \mathbb {F}$ est affine par morceaux en $x\in \Omega$, alors $F$ est fortement semi-lisse en $x$.

On peut aussi obtenir la semi-lissité d'une fonction à valeurs vectorielles si ses composantes sont semi-lisses.

Semi-lissité par composante — Soient $F_{1}:\Omega \to \mathbb {F} _{1}$ et $F_{2}:\Omega \to \mathbb {F} _{2}$ deux fonctions à valeurs dans des espaces normés de dimension finie $\mathbb {F} _{1}$ et $\mathbb {F} _{2}$ et $x\in \Omega$. Alors

$(F_{1},F_{2}):x'\in \Omega \to (F_{1}(x'),F_{2}(x'))\in \mathbb {F} _{1}\times \mathbb {F} _{2}$

est (fortement) semi-lisse en $x$ si, et seulement si, $F_{1}$ et $F_{2}$ sont (fortement) semi-lisses en $x$.

La semi-lissité est stable par composition.

Semi-lissité par composition — Si $F:\Omega \to \mathbb {F}$ est (fortement) semi-lisse en $x\in \Omega$, si $\Omega _{\mathbb {F} }$ est un voisinage de $F(x)$ dans $\mathbb {F}$ et si $G:\Omega _{\mathbb {F} }\to \mathbb {G}$ est (fortement) semi-lisse en $F(x)$, alors $G\circ F$ est (fortement) semi-lisse end $x$.

Aspects calculatoires

Un atout important de la semi-lissité est de se conserver par prise de minimum et de maximum de fonctions, ce qui n'est pas le cas de la Fréchet-différentiabilité !

Calcul — Si $F_{1}:\Omega \to \mathbb {F}$ et $F_{2}:\Omega \to \mathbb {F}$ sont (fortement) semi-lisses en $x$, alors les fonctions suivantes sont (fortement) semi-lisses en $x$ (pour les deux dernières, $\mathbb {F} =\mathbb {R} ^{m}$ et les $\max$ et $\min$ sont pris composante par composante) :

$F_{1}+F_{2},\quad \langle F_{1},F_{2}\rangle ,\quad \max(F_{1},F_{2})\quad {\mbox{et}}\quad \min(F_{1},F_{2}).$

Exemples

• Les normes $\|\cdot \|_{p}$ pour $1\leqslant p\leqslant \infty$ sont fortement semi-lisses en tout point.
• La C-fonction ${\mbox{min}}:(a,b)\in \mathbb {R} ^{2}\mapsto \min(a,b)\in \mathbb {R}$ est fortement semi-lisse en tout point.
• La C-fonction de Fischer-Burmeister $(a,b)\in \mathbb {R} ^{2}\mapsto {\sqrt {a^{2}+b^{2}}}-(a+b)\in \mathbb {R}$ est fortement semi-lisse en tout point.
• Le projecteur sur un convexe défini par des contraintes convexes de classe $C^{2}$ est fortement semi-lisse en un point du convexe satisfaisant la qualification (QC-IL) (et plus généralement la qualification de rang constant).

Annexes

Articles connexes

• Algorithme de Newton semi-lisse
• Différentiel généralisé

Références

• (en) F. Facchinei, J.-S. Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems (deux volumes). Springer Series in Operations Research. Springer.
• (en) A.F. Izmailov, M.V. Solodov (2014). Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer.
• (en) R. Mifflin (1977). Semismooth and semiconvex functions in constrained optimization. SIAM Journal on Control and Optimization, 15, 959–972.
• (en) L. Qi, J. Sun (1993). A nonsmooth version of Newton’s method. Mathematical Programming, 58, 353–367.